package sort

import "errors"

// countingSort 计数排序
func countingSort(slice []int) (result []int) {

	// 求出最大最小值，判定要排序的数据范围
	// 找到最大、最小元素
	min, max := 0, 0
	for i := 0; i < len(slice); i++ {
		if min > slice[i] {
			min = slice[i]
		}
		if max < slice[i] {
			max = slice[i]
		}
	}
	// 遍历数组，计算每个值的元素个数
	counting := make([]int, max-min+1)
	for i := 0; i < len(slice); i++ {
		counting[slice[i]-min] += 1
	}
	// 顺序求和,小于等于该值的元素的个数写入到数组中 这里该值 为 min+index
	for i := 1; i < len(counting); i++ {
		counting[i] = counting[i] + counting[i-1]
	}
	// 创建新数组以保存排序后的结果
	result = make([]int, len(slice))
	for i := 0; i < len(slice); i++ {
		count := counting[slice[i]-min]
		result[count-1] = slice[i]
		counting[slice[i]-min] = count - 1
	}

	return result
}

// bucketSort 桶排序
func bucketSort(slice []int) (result []int) {
	if len(slice) < 1 {
		return slice
	}
	// 找到最大、最小元素
	min, max := 0, 0
	for i := 0; i < len(slice); i++ {
		if min > slice[i] {
			min = slice[i]
		}
		if max < slice[i] {
			max = slice[i]
		}
	}
	// 最大值 max 最小值 min 桶中数据最多为 count 当前元素为K K 落入的坐标为 index
	// 可得到 桶大小为 (max - min + 1) / count + 1 index = (K - min) / count
	// 这里划分为 max - min + 1个桶,实际上是 count 取1 将数据挨个放入桶中
	bucketSlice := make([][]int, max-min+1)
	for i := 0; i < len(slice); i++ {
		if bucketSlice[slice[i]-min] == nil {
			bucketSlice[slice[i]-min] = make([]int, 1)
			bucketSlice[slice[i]-min][0] = slice[i]
		} else {
			bucketSlice[slice[i]-min] = append(bucketSlice[slice[i]-min], slice[i])
		}
	}
	// 各个桶排序
	for i := 0; i < len(bucketSlice); i++ {
		if bucketSlice[i] == nil {
			continue
		}
		bucketSlice[i] = quickSort(bucketSlice[i])
	}

	// 遍历各桶,排除空桶
	i := 0
	for j := 0; j < len(bucketSlice); j++ {
		bucket := bucketSlice[j]
		if bucket == nil || len(bucket) == 0 {
			continue
		}
		for k := 0; k < len(bucket); k++ {
			slice[i] = bucket[k]
			i++
		}

	}

	return slice
}

// findK 找到第K大元素
func findK(slice []int, k int) (result int, err error) {
	if len(slice) < k {
		return 0, errors.New("数组元素少于K")
	}
	if k < 1 {
		return 0, errors.New("k不能小于1")
	}

	if len(slice) == k {
		quickSort(slice)
		return slice[len(slice)-1], nil
	}
	return findKP(slice, 0, len(slice)-1, k), nil
}

// findKP 给定范围找到第K个元素
func findKP(slice []int, head int, tail int, k int) (result int) {
	// 查询范围只有一个元素，无需查找直接返回
	if tail-head == 0 {
		return slice[head]
	}
	// 思路是先分区,若分区点前账号有k-1个元素，那么分区点就是第K个元素
	point := partition(slice, head, tail)
	if point+1 == k {
		return slice[point]
	}
	// 若分区点前面的元素多于k个，则目标元素在前半部分
	if point+1 > k {
		return findKP(slice, head, point-1, k)
	}
	// 分区点前元素少于K个说明第K个元素在后半部分，在后半部分找 第 k-point-1个元素
	if point+1 < k {
		return findKP(slice, point+1, tail, k-point-1)
	}
	return 0
}

// quickSort 快速排序
func quickSort(slice []int) (result []int) {

	quickSortP(slice, 0, len(slice)-1)
	return slice
}

// quickSortP 局部排序
func quickSortP(slice []int, head int, tail int) {
	// 元素少于两个，退出递归
	if head >= tail {
		return
	}
	// 找到分区坐标
	point := partition(slice, head, tail)
	quickSortP(slice, head, point-1)
	quickSortP(slice, point+1, tail)
}

// partition 找到分区坐标
func partition(slice []int, head int, tail int) (point int) {

	// 取tail坐标值为分区值
	value := slice[tail]
	// point表示分区点坐标，分区点起始为最左侧
	point = head
	for j := head; j < tail; j++ {
		// 发现比分区点数据小的数据，将该小元素放置在分区点，并将分区点后移一位，相当于将其放置在分区点左侧
		// 循环结束，分区点右侧都是大于等于分区元素的值
		if slice[j] < value {
			// 将该小元素放置在分区点
			tmp := slice[point]
			slice[point] = slice[j]
			slice[j] = tmp
			// 分区点后移一位
			point++
		}
	}
	// 将分区元素放置在分区点
	slice[tail] = slice[point]
	slice[point] = value
	return point
}

// mergeSort 归并排序
func mergeSort(slice []int) (result []int) {
	// 元素少于两个，不再拆分
	if len(slice) < 2 {
		return slice
	}
	// 拆分
	point := len(slice) / 2
	head := slice[:point]
	tail := slice[point:]

	return merge(mergeSort(head), mergeSort(tail))
}

// merge 合并有序切片
func merge(head []int, tail []int) (result []int) {

	result = make([]int, len(head)+len(tail))
	// 各自从头取出一个元素来比较大小，将较小的那个放置在新切片中
	i, j, index := 0, 0, 0
	for ; i < len(head) && j < len(tail); index++ {
		if head[i] <= tail[j] {
			result[index] = head[i]
			i++
		} else {
			result[index] = tail[j]
			j++
		}
	}
	// 有未添加完的元素
	for ; i < len(head); index++ {
		result[index] = head[i]
		i++
	}
	for ; j < len(tail); index++ {
		result[index] = tail[j]
		j++
	}

	return result
}

// selectionSort 选择排序
func selectionSort(array *[100000]int) (result *[100000]int) {

	// 同样，数组分为待排序和已排序，每次将未排序区间最小值放置在未排序区间头部
	// 外层控制已排序和未排序的边界，内层用于找到未排序区间最小值下标
	for i := 0; i < 100000-1; i++ {
		// 找到未排序区间最小值所在下标
		j := i
		for index := i + 1; index < 100000; index++ {
			if array[index] < array[j] {
				j = index
			}
		}
		// 将未排序区间最小值与未排序区间第一个值交换位置，未排序区间向后挪一位
		if j != i {
			value := array[i]
			array[i] = array[j]
			array[j] = value
		}
	}

	return array
}

// insertionSort 插入排序
func insertionSort(array *[100000]int) (result *[100000]int) {

	// 外层循环控制未排序区间与已排序区间的边界,i为待插入数据下标，0 ～ i-1 为已排序区间
	for i := 1; i < 100000; i++ {
		// 先取出待插入数据，再从头向后找到要插入的位置
		value := array[i]
		j := i - 1
		for ; j >= 0; j-- {
			// 将比i下标数据大的数据逐一后移一位
			if array[j] > value {
				array[j+1] = array[j]
			} else {
				break
			}
		}
		// 退出循环时，j 位置上数据小于等于value，上次进入循环已经空出了j+1位置，这里将其值设置为value
		array[j+1] = value
	}

	return array
}

// bubbleSort 冒泡排序
func bubbleSort(array *[100000]int) (result *[100000]int) {

	// 从第一个元素开始比较,每一轮比较确定最后一个元素的值
	// 外层控制循环的结束位置 数组长度减循环次数
	for i := 0; i < 100000; i++ {
		// 推出循环的标志
		complete := 0
		for j := 0; j < 100000-i-1; j++ {
			if array[j] > array[j+1] {
				tmp := array[j]
				array[j] = array[j+1]
				array[j+1] = tmp
				complete++
			}
		}
		if complete == 0 {
			break
		}
	}

	return array
}
